#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;
typedef unsigned long long ull;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int N = 1e5+10;
const int mod = 19491001;
const int bas = 13331;

char s[N],t[N];
ull hs[N],ht[N],p[N];
int n,m,ans;

bool iseq(int l1,int r1,int l2,int r2){
	int len = r1 - l1 + 1;
	ull s1 = ((hs[r1] - p[len] * hs[l1-1] % mod) + mod) % mod;
	ull s2 = ((ht[r2] - p[len] * ht[l2-1] % mod) + mod) % mod;
	return s1 == s2;
}

void find(int &ps,int &pt){
	int l = 0,r = m - pt;
	while(l <= r){
		int mid = (l+r)>>1;
		if(iseq(ps,ps+mid,pt,pt+mid)) l = mid+1;
		else r = mid-1;
	}
	ps += l; pt += l;
}

bool check(int x){
	int ps = x,pt = 1;
	for(int i = 1;i <= 4 && pt <= m;i++) {find(ps,pt);if(i < 4) ps++,pt++;}
	return pt > m;
}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	int test = in;
	while(test--){
		scanf("%s",s+1); scanf("%s",t+1);
		n = strlen(s+1); m = strlen(t+1); ans = 0;
		for(int i = 1;i <= n;i++) hs[i] = (hs[i-1] * bas + s[i]) % mod;
		for(int i = 1;i <= m;i++) ht[i] = (ht[i-1] * bas + t[i]) % mod;
		for(int i = (p[0] = 1);i <= n;i++) p[i] = p[i-1] * bas % mod;
		for(int i = 1;i <= n - m + 1;i++){
			if(check(i)) ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}

